题目分析

这又是一个字符串类型的题目，如果k = 1，是什么情况？如果k != 1是什么情况？

计数排序+最小表示法

我们先分析k != 1的情况，k != 1，我的第一感觉就是字符串可以任意排序，k>2是k=2的特殊场景，我们如果能证明k=2时可以任意排序，那么k>2的场景也一定可以任意排序。

我们如果能证明可以任意交换两个相邻的字符串，那么就可以证明字符串可以任意排序。因为我们可以通过有限次交换，将需要的字符移到索引0，可以再通过有限次交换，将下一个需要的字符移到索引1，一直下去一定能够得到任意的字符串。

下面证明k = 2时，可以将ABC…PQ…XYZ经过有限次交换得到ABC…QP…XYZ。

可以先将P前面的所有字符逐个移动到最后，变成PQ…XYZABC…
再移动第二个字符Q到最后，然后移动第一个字符P到最后，变成…XYZABC…QP
最后将ABC前面的所有字符逐个移动到最后，变成ABC…QP…XYZ

所以k = 2时，我们直接对字符串进行排序即可。通过计数排序，可以将时间复杂度和空间复杂度降到$O(n)$

当k = 1时，需要对比n个字符串的大小，取最小的那一个，时间复杂度为O(n^2)，空间复杂度为O(1)

我们要思考如何降低k = 1的时间复杂度，令left表示当前最小的字符串起始索引，right表示将要比较的字符串起始索引，k表示连续相等的字符串长度，s[x]表示字符串s中的x个索引对应的字符，ss[x]表示以第x个索引开头的字符串。符合如下图的规则。

将下图的表示用算法实现即可，这里不做过多赘述，直接看图即可理解。

算法的**时间复杂度为$O(n)$，空间复杂度是$O(1)$**。

下面是Java语言的题解

class Solution {
    public String orderlyQueue(String s, int k) {
        return k == 1 ? miniExpression(s) : countSort(s);
    }

    private String miniExpression(String s) {
        int left = 0;
        int right = 1;
        int k = 0;
        int len = s.length();
        while (left < len && right < len && k < len) {
            char leftChar = s.charAt((left + k) % len);
            char rightChar = s.charAt((right + k) % len);
            if (leftChar < rightChar) {
                right += k + 1;
                k = 0;
            } else if (leftChar > rightChar) {
                left += k + 1;
                right = left + 1;
                k = 0;
            } else {
                k++;
            }
        }
        return s.substring(left, len) + s.substring(0, left);
    }

    private String countSort(String s) {
        int[] alpha = new int[26];
        for (char c : s.toCharArray()) {
            alpha[c - 'a']++;
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            builder.append(String.valueOf((char) ('a' + i)).repeat(alpha[i]));
        }
        return builder.toString();
    }
}

刷题总结

这个题目只要想到了k!=1时，可以直接排序，就能够AC本题，只不过k=1时有更好的解法优化时空复杂度。感兴趣的小伙伴可以多掌握一些解题技巧。